package 树.二叉树最大深度;

import java.util.Stack;

/**
 * @Program:IntelliJ IDEA
 * @description:
 * @author:香蕉你个啵娜娜 l.h-p@qq.com
 * @create:2023-01-06 11:32
 **/

public class Solution {
    public int maxDepth(TreeNode root){
        if (root == null){
            return 0;
        }
        /**
         * stack记录的是节点，而level中的元素和stack中的元素是
         * 同时入栈和同时出栈，并且level记录的是节点在第几层
         */
        Stack<TreeNode> stack = new Stack<>();
        Stack<Integer> level = new Stack<>();
        stack.push(root);
        level.push(1);
        int max = 0;
        while (!stack.isEmpty()) {
            // stack中的元素和level中的元素同时出栈
            TreeNode node = stack.pop();
            int temp = level.pop();
            max = Math.max(temp, max);
            if (node.left != null){
                // 同时入栈
                stack.push(node.left);
                level.push(temp + 1);
            }
            if (node.right != null){
                // 同时入栈
                stack.push(node.right);
                level.push(temp + 1);
            }
        }
        return max;
    }
}
